package org.cabbage.lintcode;

/**
 * 跟进“搜索旋转排序数组”，假如有重复元素又将如何？
 * <p>
 * 是否会影响运行时间复杂度？
 * <p>
 * 如何影响？
 * <p>
 * 为何会影响？
 * <p>
 * 写出一个函数判断给定的目标值是否出现在数组中。
 *
 * @author gezhangyuan
 */
public class Search2 {

    private boolean has = false;

    public static void main(String[] args) {
        Search2 search = new Search2();
        System.out.println(search.search(new int[]{9, 5, 6, 7, 8, 9, 9, 9, 9, 9, 9}, 8));
    }

    public boolean search(int[] A, int target) {
        if (A.length == 0) {
            return has;
        }
        searchBinch(A, target, 0, A.length - 1);
        return has;
    }

    private void searchBinch(int[] A, int target, int begin, int end) {
        if (has) {
            return;
        }
        int t = (begin + end) / 2;
        int temp = A[t];
        if (temp == target) {
            has = true;
            return;
        }
        if (begin == end) {
            return;
        }
        if (target > temp && target <= A[end]) {
            searchBinch(A, target, t + 1, end);
            return;
        }
        if (target < temp && target >= A[begin]) {
            searchBinch(A, target, begin, t);
            return;
        }
        if (Math.abs(temp - A[begin]) > Math.abs(A[end] - temp)) {
            searchBinch(A, target, begin, t);
        } else if (Math.abs(temp - A[begin]) < Math.abs(A[end] - temp)) {
            searchBinch(A, target, t + 1, end);
        } else {
            searchBinch(A, target, begin, t);
            searchBinch(A, target, t + 1, end);
        }
    }
}
